from typing import *
from math import inf


class Solution:

    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        L = [0] * n
        L[0] = arr[0]
        for i in range(n - 1):
            L[i + 1] = max(L[i] + arr[i + 1], arr[i + 1])
        R = [0] * n
        R[n - 1] = arr[n - 1]
        for i in range(n - 1, 0, -1):
            R[i - 1] = max(R[i] + arr[i - 1], arr[i - 1])
        ans = max(L[0], R[0], L[n - 1], R[n - 1])
        for i in range(1, n - 1):
            ans = max(ans, L[i], R[i], L[i] + R[i + 1], L[i - 1], R[i + 1],
                      L[i - 1] + R[i + 1])
        return ans


class Solution:

    def maximumSum(self, arr: List[int]) -> int:

        n = len(arr)
        l = [0] * n
        l[0] = arr[0]
        for i in range(1, n):
            l[i] = max(arr[i], arr[i] + l[i - 1])
        ans = arr[0]
        R = -inf
        for i in range(n - 1, 0, -1):
            ans = max(ans, arr[i], l[i], arr[i] + R)
            ans = max(ans, l[i - 1], R, l[i - 1] + R)
            R = max(arr[i], R + arr[i])
        return ans


class Solution:

    def maximumSum(self, arr: List[int]) -> int:
        a, b = arr[0], 0
        ans = arr[0]
        for i in range(1, len(arr)):
            b = max(a, b + arr[i])
            a = max(arr[i], arr[i] + a)
            ans = max(ans, a, b)
        return ans


